import java.util.Random;

public class Leetcode398 {
    public static void main(String[] args) {
        Solution s = new Solution(new int[]{1, 2, 3, 3, 3});
        System.out.println(s.pick(3));
    }

    static class Solution {

        private final int[] nums;
        private final Random random = new Random();

        public Solution(int[] nums) {
            this.nums = nums;
        }

        public int pick(int target) {
            int res = 0;
            int count = 1;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == target) {
                    if (random.nextInt(count) == 0) {
                        res = i;
                    }
                    ++count;
                }
            }

            return res;
        }
    }


}
